Python Snippet: Build from Postfix

# The basic building block for our tree.
class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# The main function to build the tree.
def build_expression_tree(postfix):
    stack = []
    operators = set(['+', '-', '*', '/'])

    for token in postfix:
        if token not in operators:
            # If the token is a number (operand),
            # create a node and push it onto the stack.
            node = Node(token)
            stack.append(node)
        else:
            # If the token is an operator, pop two
            # children from the stack. The first one
            # popped is the right child.
            right_child = stack.pop()
            left_child = stack.pop()
            
            # Create a new parent node for them.
            node = Node(token, left_child, right_child)
            
            # Push the new subtree back onto the stack.
            stack.append(node)
            
    # The final tree is the only item on the stack.
    return stack[0]